Chord

标签

分布式/P2P 与路由

字数

12961 字

阅读时间

52 分钟

Chord（SIGCOMM 2001）是这批四篇里最基础的一篇，也是把 一致性哈希 从"需要每个节点知道几乎所有其他节点"改造成"每个节点只需要 $O(\log N)$ 个邻居"的那一步。它的适用范围就一句话：

Chord 协议只支持一个操作：给定一个 key，把它映射到一个节点上。 至于那个节点是否负责存这个 key 对应的值，取决于用 Chord 的应用。

三条卖点：简单、可证明正确、可证明性能。其中"可证明正确"有个很值得记住的强弱：

对保证查询的正确（虽然慢）路由而言，每个节点只需要一条信息是正确的 —— 它的 successor 指针。

系统模型：五个要解决的问题与一条职责边界

它覆盖的五个问题：负载均衡（Chord 充当一个分布式哈希函数）、去中心化（没有节点比别的更重要）、扩展性（查找代价随节点数取对数，且不需要任何参数调节）、可用性（自动调整内部表以反映新加入与失败，即使系统持续变化）、键空间扁平（对 key 的结构不加任何约束，于是应用在把自己的名字映射到 Chord key 时有很大自由度）。

职责边界是这一节里最容易被忽略但最要紧的一点。Chord 以库的形式提供，应用与它只有两个交互面：lookup(key) 返回负责该 key 的节点的 IP 地址；每个节点上的 Chord 软件把"该节点负责的 key 集合发生了变化"通知应用（这样应用可以在新节点加入时把对应的值搬过去）。而

认证、缓存、复制、以及用户友好的命名，都由使用 Chord 的应用自己负责。

换句话说，Chord 本身不做数据复制 —— 后面那个 successor list 是为了保证环的连通性，与数据副本是两件事。应用侧可以自己复制，办法是把同一份数据存在两个不同的 Chord key 下。

一致性哈希：m 位标识符与 successor

一个节点和一个 key 各被分配一个 $m$ 位的标识符，用 SHA-1 这类基础哈希函数产生：节点的标识符由它的 IP 地址哈希而来，key 的标识符由 key 哈希而来。标识符在模 $2^m$ 的标识符环上排序，然后：

key $k$ 被分配给"标识符等于 $k$、或在标识符空间中紧随 $k$ 之后"的第一个节点。这个节点称为 $k$ 的 successor，记作 $\text{successor}(k)$。

一个 $m=6$、10 个节点、5 个 key 的环上：identifier 10 的 successor 是 node 14，所以 key 10 落在 node 14 上；keys 24 与 30 落在 node 32 上、key 38 落在 node 38 上、key 54 落在 node 56 上。

加入与离开的搬动量（引自一致性哈希那两篇）：

定理 4.1：对任意 $N$ 个节点与 $K$ 个 key 的集合，以高概率成立：① 每个节点最多负责 $(1+ϵ)K/N$ 个 key；② 当第 $N+1$ 个节点加入或离开时，只有 $O(K/N)$ 个 key 的归属发生变化（且只涉及这个加入或离开的节点）。

对 ② 还有一句定性：这显然是为了维持负载均衡所必需的最小搬动量。而 ① 里的 $ϵ$ 在按上述方式直接实现时是 $O(\log N)$；一致性哈希的原始方案里，让每个节点运行 $O(\log N)$ 个各带独立标识符的虚拟节点，可以把 $ϵ$ 压到任意小的常数。

「以高概率」这个措辞的处理方式

这一小段很短，但我觉得是 Chord 与后来许多工程系统分道扬镳的地方，值得单独记：

一致性哈希原稿用 $k$-universal 哈希函数来保证即便 key 非随机也有某些性质。Chord 选择用标准的 SHA-1 作为基础哈希函数 —— 这使协议变成确定性的，于是"以高概率"这个说法不再成立。但有一条替换论证：构造一组在 SHA-1 下碰撞的 key，在某种意义下等同于求逆（"解密"）SHA-1，而这件事被认为是困难的。所以

我们不再宣称定理"以高概率"成立，而改为宣称它们**"基于标准困难性假设"成立**。

代价是负载：为简化（主要是为了叙述）虚拟节点的使用被放弃，此时一个节点的负载可能以高概率（或按上述，基于标准困难性假设）超出平均值最多 $O(\log N)$ 倍。不放弃虚拟节点也有一条实用做法：如果对系统规模取一个先验上界（例如假定每个 IPv4 地址最多一台 Chord 服务器），那么每台物理节点跑 32 个虚拟节点就能提供很好的负载均衡。

第一步：只靠 successor 指针的朴素查找

最省状态的查找是每个节点只知道自己当前的 successor：查询沿着 successor 指针在环上一跳一跳传递，直到遇到一对"跨住"目标标识符的节点，这对里的第二个就是查询要映射到的节点。

这一版的代价是消息数与节点数成线性，但它是整个协议的地基：只要每个节点知道正确的 successor，正确性就成立。

finger table：把线性变对数

每个节点 $n$ 维护一张最多 $m$ 项的finger table。第 $i$ 项的定义是：

$$\text{finger}[i]=\text{successor}(n+2^{i-1}),1\le i\le m(\text{模 }{2}^m)$$

即从 $n$ 起至少前进 $2^{i-1}$ 的第一个节点。一项里同时含该节点的 Chord 标识符与 IP 地址（和端口号）。$n$ 的第 1 个 finger 就是它在环上的直接 successor，通常直接把它称作 successor；另定义 predecessor 为环上的前一个节点。

这个结构有两个特征：

1. 每个节点只存少数其他节点的信息，而且对环上紧随其后的节点知道得比远处的更细；这一点是它的代价来源 ——
2. 一张 finger table 通常不足以直接判定任意 key 的 successor。例子很干脆：图里的 node 8 无法自己确定 key 34 的 successor，因为那个 successor（node 38）根本不在 node 8 的 finger table 里。

查找时，$n$ 先看 id 是否落在 $(n,n.\text{successor}]$ 里，是就返回自己的 successor；否则在 finger table 里找"最紧邻地前于 id"的那个节点 $n^{\prime }$，把查询转给它。选 $n^{\prime }$ 的理由是：$n^{\prime }$ 离 id 越近，它对 id 所在那一段环就知道得越多。

例子：node 8 查 key 54 → node 8 里前于 54 的最大 finger 是 node 42 → 转给 42；42 里前于 54 的最大 finger 是 node 51 → 转给 51；51 发现自己的 successor（node 56）跨过了 54，返回 56。

「折半」这个论证

因为 finger 项按 2 的幂分布在环上，每个节点能把查询沿"到目标的剩余距离"至少推进一半。这个证明值得跟一遍：

设 $n$ 要查 $k$ 的 successor，$p$ 是紧邻 $k$ 之前的节点。设 $p$ 落在 $n$ 的第 $i$ 个 finger 区间内。这个区间非空，所以 $n$ 会指向该区间里的某个节点 $f$。$n$ 到 $f$ 的距离至少是 $2^{i-1}$；而 $f$ 与 $p$ 同处 $n$ 的第 $i$ 个 finger 区间内，所以它们之间的距离至多是 $2^{i-1}$。于是 $f$ 到 $p$ 的距离至多是 $n$ 到 $p$ 距离的一半。

每步折半、初始距离至多 $2^m$，所以 $m$ 步内距离必为 1。再加上标识符随机的假设：$\log N$ 次转发后，当前查询节点与 $k$ 的距离缩到至多 $2^m/N$，这个大小的区间里期望只有 1 个节点标识符、且以高概率是 $O(\log N)$ 个 —— 即便剩余步骤每次只前进一个节点，也能在再 $O(\log N)$ 步内跨完并到达 $k$。于是：

定理 4.2：以高概率（或在标准困难性假设下），在 $N$ 个节点的网络中，为找到一个 successor 需要接触的节点数是 $O(\log N)$。

加入与稳定化

join(n')（$n^{\prime }$ 是任意已知的 Chord 节点）按顺序做四步：predecessor = nil、请 $n^{\prime }$ 找出 $n$ 的直接 successor $s$、build_fingers(s)、successor = s。注意 join() 自己并不会让网络其余部分知道 $n$ 的存在。

真正让别人知道的机制是每个节点周期性地跑 stabilize()：

• stabilize()：问自己的 successor 要它的 predecessor $p$，判断 $p$ 是否应该成为自己的 successor（如果 $p$ 是刚加入的就会这样）；然后**successor.notify(n)**，给 successor 一个机会把 predecessor 改成自己；
• notify(n')：若 predecessor 为空、或 $n^{\prime }\in (\text{predecessor},n)$，则把 predecessor 设为 $n^{\prime }$。

一个刚加入的、还没被任何 finger 指到的新节点会让查询短暂地"打偏"（undershoot），但查找算法里的循环会顺着 successor（即 finger[1]）指针穿过这些新节点直到正确的 predecessor；等 finger table 被修好，这种线性扫描就不再需要。

定理 4.3：若把任意序列的 join 操作与 stabilization 交错执行，那么在最后一次 join 之后的某个时刻，successor 指针会在网络中所有节点上形成一个环。

稳定化没完成时查找的三种行为

情形	结果
常见情形：涉及的 finger 项还比较新	$O(\log N)$ 步内找到正确的 successor
successor 指针正确，但 finger 不准确	查找仍然正确，但可能更慢
受影响区域的节点 successor 指针不正确，或 key 还没迁到新加入的节点	查找可能失败，上层软件会发现取不到数据，可以停顿一下重试（这个停顿可以很短，因为稳定化很快就修好 successor 指针）

这里有一个看起来反直觉的性质：finger 项能把查询送出很远，这件事并不取决于它指向的到底是哪个节点 —— 折半论证只依赖标识符空间里的距离。所以 finger 过期并不会显著拖慢查找。新加入节点影响速度的唯一主要途径是它的 ID 落在目标 predecessor 与目标之间，此时查询得一个个穿过去；除非有极大量节点同时加入，两个老节点之间的新节点通常很少。形式化后就是：

定理 4.4：取一个含 $N$ 个节点的稳定网络，再加入最多 $N$ 个节点，若所有 successor 指针正确（但 finger 指针未必），那么查找仍以高概率耗时 $O(\log N)$。

更一般地：只要把 finger 调整好所花的时间少于网络规模翻倍所花的时间，查找就一直是 $O(\log N)$ 跳 —— 这可以通过反复执行查找来更新 finger 达成，于是只要在任意 $N$ 次节点加入之间发生 ${\log }^{2}N$ 轮稳定化，查找的表现就良好。

失败、successor list 与自愿离开

正确性依赖"每个节点知道自己的 successor"这条不变量，而节点失败会破坏它。 一个例子很具体：若节点 14、21、32 同时失败，node 8 就不知道 node 38 现在是它的 successor（因为它没有任何 finger 指向 38）—— 于是一个发给 node 8 的 key 30 查询会错误地返回 node 42，而不是正确的 successor node 38。

对策是每个节点维护一个长度为 $r$ 的 successor list，存它的前 $r$ 个 successor：直接 successor 不响应就换列表里的第二项。于是必须 $r$ 个 successor 同时失败才会打断环，而这在适中的 $r$ 下已经极不可能。实现应当取固定的 $r=2{\log }_{2}N$（按可预见的系统规模上限 $N$ 算）。

列表的维护方式是：节点 $u$ 与它的 successor $s$ 对账 —— 把 $s$ 的列表 $\ell$ 抄过来、把 $s$ 加到 $\ell$ 的最前面、再删掉最后一个元素。节点发现 successor 失败时，用 successor list 里第一个存活的项替换它，并和新 successor 对账；此后它就能把"原本该由失败节点负责"的查询直接指向新 successor。随时间推移，stabilize 会把指向失败节点的 finger 与 successor list 项都修掉。另外，closest_preceding_node 要同时搜 finger table 与 successor list；find_successor 中途遇到节点失败时，超时后从 finger table 与 successor list 里试下一个最好的 predecessor。

定理 4.5：在一个初始稳定的网络中，若使用长度 $r=O(\log N)$ 的 successor list、然后每个节点以概率 $1/2$ 失败，那么以高概率 find_successor 仍返回查询 key 最近的存活 successor。

证明只有一句：失败前每个节点知道自己的 $r$ 个后继，这 $r$ 个全部失败的概率是 $(1/2{)}^r$。

自愿离开可以直接当成失败处理，但有两条增强：① 离开前把 key 交给自己的 successor；② 离开前通知自己的 predecessor $p$ 与 successor $s$。于是 $p$ 把 $n$ 从 successor list 里删掉、并把 $n$ 的 successor list 的最后一个节点加进自己的列表；$s$ 用 $n$ 的 predecessor 替换掉自己的 predecessor（前提：$n$ 把自己的 predecessor 发给 $s$、把 successor list 里的最后一个节点发给 $p$）。

正确性分析（一）：lookup 最终一定会成功

第 4 章的定理只在几个简单模型下成立（节点停止加入后的最终稳定、稳定环面对失败）。第 5 章放宽到节点持续加入与离开的模型，要证两件事：系统保持稳定，且查找继续可用且快。全章都建立在一条通信假设上：任意两个试图通信的节点最终都能成功。

两条"最终会好"的定理先立起来：

定理 5.1：一旦某个节点能成功解析某个查询，它此后将永远能解析该查询。

定理 5.2：在最后一次加入之后的某个时刻，所有 successor 指针都会是正确的。

它们的证明靠一条不变量 + 一个终止性论证。不变量是"一旦节点 $n$ 能经 successor 指针到达节点 $r$，它就永远能"；终止性论证是：两个节点都以为自己的 successor 是 $s$ 时，各自都会去 notify $s$，$s$ 最终会选两者中更近的那个（或某个更近的节点）作为 predecessor —— 而此时较远的那个会通过联系 $s$ 得知一个比 $s$ 更好的 successor。于是每个节点都在朝"更好的 successor"演进，这种演进必须终止于"每个节点恰好是另一个节点的 successor"的状态 —— 那定义了一个环（也可能是几个环，但不变量保证了至多一个）。

形式化这个论证需要先定义两个概念：

定义	内容
5.3 reachable	从 $p$ 出发沿 successor 指针走最终能到达 $s$，则称 $s$ 从 $p$ 可达，也说 $p$ 能到达 $s$
5.4 arc path	从 $p$ 到 $s$ 的 arc path 是"只经过 $p$ 与 $s$ 之间那些节点"的一条从 $p$ 到 $s$ 的 successor 指针路径

"只经过 $p$ 与 $s$ 之间的节点"这个限定是整套证明的支点 —— 它让"指针变化不会破坏可达性"这件事可以被局部地论证。

引理 5.5：若某时刻 $t$ 存在从 $p$ 到 $s$ 的 arc path，则其后所有 $t^{\prime }>t$ 时刻都存在从 $p$ 到 $s$ 的 arc path。

证明是对时间做归纳（把时间看作"successor / predecessor 指针的变化次数"）。原证明里最关键的两步：

1. 节点加入会建立一条 successor 指针，让它能到达此前到不了的节点，但显然不破坏任何已有的 arc path。
2. 稳定化这一步要论证。设节点 $p$ 把 successor 从 $s$ 改成 $a$ —— 这只可能是因为 $p$ 联系了 $s$ 并听说了 $a$，且 $p<a<s$。那么在更早的某个时刻，$s$ 得知了 $a$，而这只可能是 $a$ 告诉了 $s$ 关于自己的信息，而这又只可能在某个更早时刻 $a$ 的 successor 是 $s$ 时发生 —— 在那个时刻，存在从 $a$ 到 $s$ 的 arc path（就是那条 successor 链）。由归纳，在 $p$ 把指针改向 $a$ 之前，从 $a$ 到 $s$ 的 arc path 仍然存在。而因为 $p<a<s$，这条从 $a$ 到 $s$ 的 arc path 不可能包含 $p$ —— 于是 $p$ 改指针这件事没有扰动它。把边 $(p,a)$ 与这条 arc path 接起来，就得到一条从 $p$ 到 $s$ 的 arc path。
3. 最后还要处理"别的 arc path 里用到了 $p\to s$ 这条边"的情形：既然那条路径是 arc path，$p$ 与 $s$ 必然都在它的端点 $x$ 与 $y$ 之间；而刚刚证明了新的 $p\to s$ 路径上所有节点都在 $p$ 与 $s$ 之间，因此也都在 $x$ 与 $y$ 之间 —— 于是那条从 $x$ 到 $y$ 的路径仍然是 arc path。

两条推论接着用：

推论 5.6：若时刻 $t$ 存在从 $a$ 到 $b$ 的 successor arc 路径，则所有 $t^{\prime }>t$ 时刻仍存在。证明：由上一条引理，路径上每条 successor arc 只会被"一条路径"替换、不会被断开；把这些替换路径接起来就是从 $a$ 到 $b$ 的路径。

推论 5.7：设 $a$ 是 Chord 网络中第一个节点，则在任何时刻，每个节点都能经 successor 指针到达 $a$。证明对加入次数做归纳：新节点加入时其 successor 指针指向一个能到达 $a$ 的节点，故新节点也能到达 $a$；再由上一条，既然新节点起初能到达 $a$，它就永远能。

有了这两条才能收口：

定理 5.8：若把任意序列的 join 操作与 stabilization 交错执行，则在最后一次 join 之后的某个时刻，successor arc 会在网络中所有节点上形成一个环。

证明：注意到若两个节点共享同一个 successor，其中一个最终会改自己的 successor 指针；它的新 successor 在环上比旧的更近，所以它的 successor 指针最多变化 $n$ 次。于是在 $n^2$ 步之后，必然进入一个稳定状态：每个节点至多是（因而恰好是）一个节点的 successor。而每个节点又恰好有一个 successor，所以满足"入度 1 且出度 1"的图结构只能是一组环。但由不变量，每个节点都能到达网络中最早出现的那个节点 —— 所以这组环只能恰好是一个环。

加入对查找性能的影响：finger 为什么不慌

一个反直觉的结论：节点加入时 finger 的调整不需要专门讨论，因为加入并不会实质伤害 finger 的性能。

若一个节点在每个区间都有一项 finger，那么即便有节点加入，这些 finger 仍然可用。折半论证基本不变，仍能说明 $O(\log N)$ 跳就足以到达"接近"查询目标的节点。

新加入节点影响查找的唯一途径是它落在目标查询的旧 predecessor 与 successor 之间 —— 这些新节点可能需要被线性扫过（如果它们的 finger 还不准）。但除非有极大量节点同时加入，两个老节点之间的新节点很可能非常少，因此影响可以忽略。形式化后：

定理 5.9：取一个含 $N$ 个节点的稳定网络，再加入最多 $N$ 个**没有 finger 指针（但 successor 指针正确）**的节点，则查找仍以高概率耗时 $O(\log N)$。

证明：原有那批 finger 会在 $O(\log N)$ 时间内把查询带到正确节点的旧 predecessor；而以高概率，任意两个老节点之间落下的新节点至多 $O(\log N)$ 个 —— 所以从旧 predecessor 走到新 predecessor，沿 successor 指针只需要穿过 $O(\log N)$ 个新节点。

这个结论可以推广成一条更好用的判据：只要"调整 finger 所花的时间"小于"网络规模翻倍所花的时间"，查找就会一直是 $O(\log N)$ 跳；而这一点可以靠反复执行查找来更新 finger 达成 —— 于是

只要在任意 $N$ 次节点加入之间发生 ${\log }^{2}N$ 轮稳定化，查找的表现就良好。

强稳定化：weak / strong / loopy 三个定义

这是全篇最深的一段，常规的 Chord 介绍几乎都不提。先看 stabilize() 保证的性质：

stabilize() 试图保证的，是对任意节点 $u$ 都有 $\text{predecessor}(\text{successor}(u))=u$。这是一个局部一致性条件，对 Chord 网络的正常行为而言必要但不充分。

一个反例：某个 Chord 网络在这个协议下是稳定的，但全局不一致 —— 事实上不存在任何节点 $u$ 使得 $\text{successor}(u)$ 是环上紧随 $u$ 的第一个节点。于是有了三个定义：

名称	定义
弱稳定（weakly stable）	对所有 $u$，$\text{predecessor}(\text{successor}(u))=u$
强稳定（strongly stable）	在弱稳定基础上，对每个 $u$，其所在分量中不存在满足 $u<v<\text{successor}(u)$ 的节点 $v$
环套（loopy）	弱稳定但非强稳定

之所以要往强稳定这一层深挖，有两条很务实的警惕：实现里的一个 bug 可能导致环套状态；或者模型本身失效 —— 例如某节点失联太久，以致一些节点认为它已失败，而它自己仍确信自己活着，这种相互矛盾的意见可能把系统带进奇怪的状态。所以需要的是一个能从任意状态稳定下来的协议，哪怕那个状态不可能由协议的正确运行产生。

核心操作是 self-search：节点 $u$ 在网络中查找自己。如果网络是环套的，那么从 $u$ 出发的自查找会沿环走一圈，然后找到环上"紧随 $u$ 之后的第一个节点" —— 也就是沿 successor 指针走时第一个满足 $\text{predecessor}(w)<u<w$ 的节点 $w$。图 9 那版协议因此把每个节点的后继从 1 个变成 2 个（successor[0]、successor[1]）并加一个 on cycle 标志，用自查找把环套的环"解开"（unfurl）。

这个协议的边界也划得很清：

该协议不试图重连一个已经断开的网络；那要依赖某种外部手段。

这条限制在 Future Work 里被再确认了一次：Chord 目前没有专门的机制去自愈被分区的环，因为这种环对稳定化过程来说可能是局部一致的。一个检测思路：让每个节点 $n$ 周期性地请别的节点替它做一次 Chord 查找；若查出来的不是 $n$，就可能存在分区 —— 但这只能检出其节点互相知道的分区。另外两条思路是让所有节点都知道同一小组初始节点，或让节点长期记住它曾遇到过的一小组随机节点。

强稳定化的收敛速度与证明结构

协议的代价是明确的：

定理 5.11：任何连通的 Chord 网络在 $O(N^2)$ 轮强稳定化之内变为强稳定。

$O(N^2)$ 很慢，但有一条关键辩护：环套状态本身是极低概率事件，所以在系统的无限生命里，用于从环套状态恢复的时间可以忽略。

证明的两条直觉合起来说明"网络唯一稳定的构型就是想要的那个"：

1. 首先排除"错的弱稳定"：若网络弱稳定但非强稳定，则至少有一个节点在对自己做搜索时会找到一个更好的第二 successor；
2. 再排除"非环套"（即某些节点有不止一个 successor 指针）：每个节点至少有一个 successor 指针，所以系统里至少有 $N$ 个指针；只要有一个节点的两个指针不同（successor[0] != successor[1]），系统里就有超过 $N$ 个不同的 successor 指针 —— 于是由鸽巢原理，某个节点 $s$ 会被两个不同的节点当作 successor；而这不是稳定状态：更近的那个 predecessor $p$ 最终会 notify $s$，之后较远的那个会得知并改指向 $p$。于是唯一稳定的情形是每个节点恰好一个 successor 指针、且指向它在网络中的真实 successor。

中间那块靠两条引理与一条 claim 支撑：

引理 5.12：若网络中存在环套的环，则存在某个节点 $u$，其自查找会揭示一个满足 $u<v<\text{successor}(u)$ 的节点 $v$。

证明：设环套环为 $C$，按定义存在 $u,s\in C$ 且 $u<s<\text{successor}(u)$。因为 $C$ 是个环，从 $u$ 反复沿 successor 指针走最终会到达 $s$；而由于 $u<s<\text{successor}(u)$，在标识符环的第一次遍历里是找不到 $s$ 的。更一般地，必然存在 $u,w\in C$ 使 $w$ 不在 $u$ 的 loop 上。取 $v$ 为"从 $u$ 沿 successor 指针走时第一个不在 $u$ 的 loop 上的节点"，于是 $\text{predecessor}(v)<u<v$，且 $\text{predecessor}(v)$ 在 $u$ 的 loop 上。把 $u$ 的 loop 上的节点记作 $s_0(u)=u,s_1(u),\dots ,s_{\ell }(u)$（其中 $\text{successor}(s_i)=s_{i+1}$，$s_{\ell }(u)=\text{predecessor}(v)$）。则必存在某个 $0\le i<\ell$ 使 $s_i(u)<v<s_{i+1}(u)$ —— 注意 $v$ 不能落在 $(s_{\ell }(u),u)$ 区间内，否则 $v$ 就在 $u$ 的 loop 上了。若 $i=0$，则 $u$ 的自查找直接给出一个更好的 successor $v$（因为 $u=s_0(u)<v<s_1(u)=\text{successor}(u)$）。若 $i\ge 1$，则 $s_i(u)$ 的自查找同样会给出 $v$（它是 $s_{i+1}(u)=\text{successor}(s_i(u))$ 的改进），理由是 —— $s_i(u)$ 的自查找路径是 $u$ 的自查找路径的一条子路径。

引理 5.13：arc path 在强稳定化下同样保持（证明与引理 5.5 一样对系统变化做归纳；加入与自查找只会增加一条边、不会破坏 arc path，替换一条重复的边也不会）。

Claim 5.15：若 Chord 网络连通但非强稳定，则经过 $O(1)$ 轮稳定化后，某个 successor 指针会得到改进。

证明分三种情形：① 若存在两个不同节点 $p_1<p_2$ 都以 $u$ 为 successor，则 $p_2$ 稳定化之后 $u$ 会得到一个 predecessor $p$ 满足 $p_1<p_2\le p<u$；随后 $p_1$ 稳定化时，就会把自己指向 $u$ 的指针改成指向 $p$；② 若存在节点有两个不同的 successor 指针，则共有 $n+1$ 个不同的 successor 指针，由鸽巢原理回到情形 ①；③ 否则每个节点只指向一个节点、也只被一个节点指向 —— 网络是一组环；因已假设连通，所以是单个环；又因假设非强稳定，这个环是环套的 —— 于是由引理 5.12，一轮自查找就能为某个节点找到更好的 successor。

定理 5.11 的证明接起来：推论 5.14 保证连通性在强稳定化过程中始终成立；Claim 5.15 保证"在达到强稳定之前，总能在 $O(1)$ 轮稳定化内改进某个 successor 指针"。注意任何改动了某节点 successor 指针的稳定化操作都是在"改进"它（新 successor 在标识符环上比旧的更接近该节点）。于是计数：系统里共 $2N$ 个指针（每节点两个），每个指针最多改进 $N$ 次（它只能指向 $N$ 个候选之一）—— 所以在 $O(N^2)$ 次改进之后，每个节点的两个 successor 指针都必须指向它在环上的真实 successor。

还有一个顺带得出的行为：环套的 Chord 网络在其环合并之前根本不允许新节点加入 —— 因为在环套网络中，对所有 $u$ 都有 u.on_cycle = false（$u$ 的自查找在环套网络里永远不会返回 $u$ 自己）。于是若网络以某种方式进入了环套状态，它会在 $O(N^2)$ 轮内自愈，且不受试图加入的节点干扰。

自查找那一步原本每轮要 $O(N)$ 时间，可以降到以高概率 $O(\log N)$：办法是用 finger 来搜 —— finger 可以靠指针倍增（pointer doubling）建立，或让每个节点 $u$ 对递增的 $i$ 调用 u.find_successor(u + 2^{i-1})。可以归纳地证明 $u.\text{finger}[i]$ 会落在 $u$ 的 loop 里，因此基于 finger 的搜索与只靠 successor 的搜索给出相同结果。

最后是把失败纳入进来：

定理 5.16：从一个带长度 $O(\log N)$ 的 successor list 的任意连通状态出发，允许失败以"每 $\mathrm{\Psi }(\log N)$ 步内至多 $N/2$ 个节点"的速率发生，则以高概率在 $O(N^3)$ 轮内网络变为强稳定。

这里有一个和弱稳定化不同的新风险：若 $u$ 的某个 successor 失败了，那么"失败的 successor"与"$u$ 的 successor list 里第一个存活项"之间可能隔着大量节点 —— 于是我们可能按前述"进展"的概念向后倒退。但网络清空之前最多发生 $N$ 次失败，而若在这 $N$ 次失败之后发生了 $O(N^2)$ 次改进，我们就已经强稳定，于是得到上面的 $O(N^3)$。

双环交错时的快速强稳定化

最可能造出环套图的场景是网络分区 —— 分区彻底切断了部分节点与其他节点的连通。这个问题可以用一个具体模型来研究：从一个弱稳定但由两个环组成的网络出发 —— 即从某个节点 $u$ 出发沿 successor 指针走，会恰好绕标识符环两周之后回到 $u$。

改法很小：修改 u.stabilize()，让 $u$ 在离准确定位还很远时能一次移动一大段距离 —— 允许 $u$ 移到"任何 finger 指向 $u.\text{successor}$ 的节点"，而不是只允许移到那个 predecessor。这让 $u$ 能在 $O({\log }^{2}N)$（而不是 $\mathrm{\Psi }(N)$）时间内找到它在环上的真实 successor。

正确性分析（二）：动态模型与带失败的稳定化

前面几个定理都有个隐含前提：初始状态是个环。但实践中这个前提不成立 —— 系统里总会有一些刚加入、还没来得及嵌进环里的节点。所以要证一个更强的结果：稳定化算法能让系统持续保持"类环"的状态。为叙述简单，这里限制在同步的稳定化模型下（对下述定义做一点相应调整，就可以处理"多数机器以大致相同速率运行、消息到达时间大致一致"这种程度的异步，且运行时间不增加）。

几个定义先把"不是环"的中间状态描述清楚：

概念	定义
一轮（round）	每个节点运行一次 stabilize() 所需的 $O(1)$ 时间（不计密钥迁移的时间）
pseudoforest	因为每个节点恰好有一个 successor，successor 指针定义的图必然是一个 pseudoforest —— 所有连通分量都是"朝一个根环（而不是朝一个根节点）指的"有向树
pseudotree	限制在连通网络上时，该图就是一个 pseudotree
appendage $A_u$	网络弱稳定时所有节点都在环上；对每个环节点 $u$，有一棵以 $u$ 为根的树，称为 $u$ 的 appendage

还有一条强制要求：加入的节点必须对一个已经在环上的既有节点调用 u.join(n) —— 可以靠外部设施保证这一点，或者用那个更复杂的 join() 协议。

定义 5.19（pseudostar）：满足三条的 Chord 网络 —— ① 环是非环套的；② $A_u\subseteq [p,u]$，其中 $p$ 是 $u$ 在环上的 predecessor；③ 对每个 $v\in A_u$ 都有 $u=v.\text{successor}$。

引理 5.20：从一个 pseudostar 出发，在运行 stabilize() 的同时执行任意序列的加入，得到的网络仍然是 pseudostar。

这个结论比直觉更强：它即便对完全不讲道理的加入也成立 —— 例如加入节点的标识符是被恶意挑选的、而不服从随机分布。

紧接着是那个关键的"类环状态"定义。这一串条件看起来繁琐，但每一条都对应后面某个论证要用到的性质：

定义 5.21（$c$-ring-like state）：对某个常数 $c$ —— ① 网络是 pseudostar； ② 加入网络至少 $8c^2{\log }^{2}N$ 轮的节点：(a) 全都在环上；(b) 占网络中至少一半；(c) 在标识符环上独立均匀分布；(d) 永不落入区间 $[u+2^{i-1},u.\text{finger}[i]]$； ③ 在最近 $8c^2{\log }^{2}N$ 轮内加入的节点：(a) 在标识符环上独立均匀分布；(b) 对环上任意连续节点 $u_1,\dots ,u_{\log N}$，有 $\sum _{i=1}^{\log N}|A_{u_i}|\le c\log N$。

增大常数 $c$ 会提高本节结论里 $1-1/n^{O(1)}$ 成功概率的指数。

有一处不能过度声称的地方：近期加入的节点被纳入环的顺序可能存在偏差 —— 例如"靠近已在环上的节点的节点"、以及"落在环上两个互相靠近的节点之间的节点"，会更早被纳入；所以不能说环上所有节点的分布是均匀且独立的：

出于技术原因，我们考虑一个强稳定、finger 正确、且所有节点标识符独立均匀选取的网络处于类环状态。

引理 5.22：从含 $N$ 个节点的 $c$-ring-like state 出发，允许在至少 $8c^2{\log }^{2}N$ 轮内于任意时刻发生最多 $N$ 次随机加入，则以高概率我们最终仍处在 $c$-ring-like state（要提高成功概率就把 $c$ 调大）。

证明的思路是把节点按"在线时长"分成三代："老"节点（在场超过 $8c^2{\log }^{2}N$ 轮）、"中年"节点（在场时间更短）、以及**"新"节点**（在当前这段 $8c^2{\log }^{2}N$ 轮稳定化期间加入的最多 $N$ 个）。论证链是：

1. 按定义，老节点都在环上；
2. 由标识符随机可知，任意两个老节点之间只会有 $O(\log N)$ 个节点加入；
3. 由条件 ②d，finger 指针相对于老节点是正确的 —— 即没有任何 finger 指针跳过某个老节点；
4. 于是老节点恰好扮演了上一节分析里"初始那个环"的角色：因为只加入 $N$ 个节点，指向老节点的那些 finger 就足够为新节点快速路由查找；
5. 这推出在上述时间窗内没有任何节点的 appendage 会变得过大；而既然 appendage 都不大、且每轮至少有一个节点从每个 appendage 上脱落进入环，那么在分析开始时在场的那些节点（即中年节点）都会在变成"老"之前进入环 —— 类环状态的不变量因此得以保持；
6. 中年节点全部进入环之后，还需额外 $O({\log }^{2}N)$ 轮稳定化来保证 finger 相对于中年节点也正确（由上一步可知 fix_fingers() 很快）。

失败：successor list 多久需要抄一次

先看一个纯失败的模型（这样的环显然撑不了多久，但它回答的是"successor list 该多久抄一次"）。

引理 5.23：设一个 $N$ 节点 Chord 环里每个节点都有长度 $2c\log N$ 的 successor list、且至少含有环上接下来 $c\log N$ 个存活 successor。假设任意挑选的 $N/4$ 个节点（与它们的标识符无关）在"每个节点执行 $2c\log N$ 次 successor list 复制"的这段时间内失败。那么在结束时，每个节点仍然持有一个含环上接下来 $c\log N$ 个存活 successor 的 successor list。

证明：因为失败与标识符无关，失败在标识符空间里是随机的 —— 于是以高概率，对每个 $u$，$u$ 的 successor list 里那 $c\log N$ 个活节点中至少有一个在整个这批失败期间活下来，环因此保持连通。接下来是个可以被反复引用的性质：归纳可知，出现在 $u$ 的 successor list 第 $i$ 位的节点，在 $i$ 轮之前是活着的。所以经过 $2c\log N$ 轮之后，在这批失败之前就已下线的节点不会再出现在任何 successor list 里。于是此时 $u$ 的 successor list 含有的是"在这段过程的起点活着、且位于 $u$ 之后的前 $2c\log N$ 个节点"（若其中有些随后也失败了，就由环上更远处的节点替补）。而以高概率这 $2c\log N$ 个节点里失败的不到一半，所以 $u$ 的 list 里至少含有环上接下来 $c\log N$ 个存活 successor。

把失败正式纳入类环状态，需要把定义再加固一层：

定义 5.24（robust strongly non-loopy pseudotree）：一个带 successor list 的 pseudotree，满足 ① 环是非环套的；② $A_u\subseteq [p,u]$；③ 对每个 $v\in A_u$ 有 $v<v.\text{successor}<u$；④ 若 $s=u.\text{successor}$ 的 successor list 跳过了区间 $[s,\text{last}(s.\text{successor list})]$ 中的某个活节点 $v$，则 $v$ 不在 $u$ 的 successor list 里。

引理 5.25：从一个 robust strongly non-loopy pseudotree 出发，在运行 stabilize() 的同时执行任意序列的加入与失败，则只要得到的网络仍然连通，它就仍是一个 robust strongly non-loopy pseudotree。

同样地，它即便对完全不讲道理的加入与失败也成立 —— 例如失败节点的选择与加入节点的标识符都是被恶意挑选的、不服从随机分布 —— 只要网络保持连通。

这里引出一个很实用的判据：

在 successor list 长度为 $2c\log N$ 的网络里，称节点 $u$ 完全并入（fully incorporated）环，当且仅当它已经在环上停留了至少 $2c^2\log N$ 个连续轮。

理由给得很直白：仅仅"某个环节点 $u$ 指向了节点 $v$"并不足以让 $v$ 稳健地在环上 —— 因为如果 $u$ 在设置 u.successor = v 之后立刻失败，$v$ 就会从环上掉下去。

定义 5.26（带 successor list 的类环状态）：网络有长度 $2c\log N$ 的 successor list，且 ① 每个节点的"第一个存活 successor"所定义的图是一个 robust strongly non-loopy pseudotree； ② 加入至少 $16c^5{\log }^{2}N$ 轮的节点：(a) 全部完全并入环；(b) 占至少一半；(c) 独立均匀分布；(d) 永不落入 $[u+2^{i-1},u.\text{finger}[i]]$； ③ 在最近 $16c^5{\log }^{2}N$ 轮内加入的节点：(a) 独立均匀分布；(b) 任意连续 $\log N$ 个环上节点满足 $\sum |A_{u_i}|\le c^2\log N$； ④ 每个节点 $u$ 的 successor list：(a) 不含失败超过 $16c^5{\log }^{2}N$ 轮的节点；(b) 含在最近 $16c^5{\log }^{2}N$ 轮内失败的节点不超过 $c\log N$ 个；(c) 含 $[u,\text{last}(u.\text{successor list})]$ 中每一个在至少 $16c^5{\log }^{2}N$ 轮前成功进入环的活节点； ⑤ 节点失败在所有当时存在的节点中独立均匀。

引理 5.27：在失败独立且均匀地取自所有当时存活节点的前提下，对任意 $k$，运行 stabilize() 只会降低"$u$ 的 successor list 里超过 $k$ 个节点会失败"这一事件的概率（对任意节点 $u$）。

证明（这一段解释的是"为什么抄 successor list 是有益的"，值得跟一遍）：对任意节点 $v$，考虑 $v$ 的 successor list 里第 $i$ 项 $w_i$。归纳可知 $w_i$ 在 $i$ 轮稳定化之前是活着的 —— 因为它当时被放进了 $w_{i-1}$ 的 successor list。我们不知道 $w_i$ 在刚过去的 $i-1$ 轮里是否失败。在时刻 $t$，u.stabilize() 把 $u.\text{successor}$ 调整到一个活节点 $s$，并调用 u.fix_successor_list() 把 $u$ 的 list 尾部替换成 $s$ 的 list。由上可知，$s$ 的 list 在时刻 $t-1$ 的第 $i$ 项（也就是 $u$ 的 list 在时刻 $t$ 的第 $i+1$ 项）在第 $t-1-i$ 轮是活着的；而 $u$ 的 list 里原来那个第 $i+1$ 项是在第 $t-1-(i+1)$ 轮活着的，它有可能在第 $t-1-i$ 轮失败了。在随机失败的假设下，这就意味着"$u$ 的 list 第 $i+1$ 项已经失败"的概率下降了。而若两者在时刻 $t$ 都活着，则由随机失败，其中一个在任意 $t^{\prime }>t$ 失败的概率与另一个相同。

最后一个结构性事实：当环节点 $u$ 失败时，$A_u$ 里的节点会被并入 $A_{u.\text{successor}}$ —— 称为 $A_u$ 与 $A_{u.\text{successor}}$ 合并（merged）。

评测

模拟器实现的是迭代式（由发起查找的节点发起全部通信）而非递归式（每个中间节点向下转发）。

负载均衡：一致性哈希的偏差有多大

${10}^4$ 个节点、key 总数从 ${10}^5$ 到 ${10}^6$ 递增，每个取值重复 20 次。key 数的波动随 key 总数线性增长 —— 所有情形下都有节点一个 key 都不存。 在总量 $5\times {10}^5$ 个 key 时：

指标	数值
单节点最多存的 key 数	457，即均值的 9.1 倍
第 99 百分位	均值的 4.6 倍

波动的一个原因是节点标识符并没有均匀覆盖整个标识符空间。把标识符空间分成 $N$ 个等长的桶，期望每桶一个节点 —— 但某个特定桶里没有任何节点的概率是 $(1-1/N{)}^N$，$N$ 大时趋近 $e^{-1}=0.368$。这是一个很干净的解释。

虚拟节点的实测（${10}^4$ 真实节点、${10}^6$ 个 key，$r=1,2,5,10,20$）：第 99 百分位从均值的 $4.8$ 倍降到 $1.6$ 倍，第 1 百分位从 $0$ 升到均值的 $0.5$ 倍。代价是路由表空间乘 $r$，这在实践中容易接受：$N={10}^6$ 且 $r=\log N$ 时，每个节点只需维护约 ${\log }^{2}N\simeq 400$ 项的表。另外要注意：加虚拟节点不影响最坏情况查询路径长度 —— 它变成 $O(\log (N\log N))=O(\log N)$。

路径长度：为什么是 $\frac{1}{2}{\log }_{2}N$

$N=2^k$ 个节点、共存 $100\times 2^k$ 个 key，$k$ 从 3 到 14。平均路径长度呈对数增长，实测约为 $\frac{1}{2}{\log }_{2}N$。 那个 $\frac{1}{2}$ 的来源很漂亮：

把节点到查询目标的距离用二进制表示。距离的最高位（第 $i$ 位）可以通过走该节点的第 $i$ 个 finger 修正为 0。 如果距离的下一个有效位是 1，那它也需要走一个 finger 来修正；但如果是 0，就不走第 $i-1$ 个 finger，而是直接跳到第 $i-2$ 位。一般地，需要走的 finger 数就是"节点到查询目标的距离"的二进制表示里 1 的个数。距离是随机的，所以平均而言 $\log N$ 位里有一半是 1。

同时失败

${10}^4$ 个节点、${10}^6$ 个 key，随机让比例 $p$ 的节点失败，等网络稳定完再统计查不到的 key 比例。这里"正确查找"的定义是找到失败前原本负责该 key 的节点 —— 它对应一个"存了 key 的值、但既不做复制也不在失败后恢复"的系统。

查找失败率几乎正好等于 $p$。 而这正是"负责该 key 的节点失败所导致的、本来就必然丢失的 key 占比"，所以结论是Chord 网络里没有显著的查找失败。一个很有力的对照：如果 Chord 网络裂成了大小相等的两半，我们会预期一半请求失败（因为请求方与目标有一半概率不在同一分区），而结果并非如此。

稳定化期间的查找

评估口径先声明清楚：只要查询到达了目标 key 当前的 successor 就算成功（这略偏乐观 —— 真实系统里可能存在"真正的 successor 还没来得及从旧 successor 那里拿到数据"的时段）；模拟器不重试查询，所以这一节数字可以看成状态不一致导致的查询失败的最坏情况。

参数：key 查找按每秒 1 次的泊松过程产生；join 与 failure 按均值为 $R$ 的泊松过程；每个节点以平均 30 秒的随机间隔跑稳定化（且每次调用会更新全部 finger 项）；网络从 500 个节点起步。

一个可以手算的估算：500 个节点时路径长度约 5。若 $k$ 个节点失败，其中一个落在 finger 路径上的概率大致是 $5k/500$，即 $k/100$ —— 于是若两次稳定化之间有 3 个失败，失败率约为 3%。图上的结果确实在这个量级附近，但略差一些，因为把某个失败节点彻底清出去可能需要不止一次稳定化。

Internet 原型

部署在美国 RON 测试床的十个站点上（加州、科罗拉多、马萨诸塞、纽约、北卡、宾州），跑在 UNIX 上，用 SHA-1 生成的 160 位 key，节点间用 TCP，采用迭代式。节点数超过 10 的实验靠在每个站点跑多份独立副本来做 —— 注意这不同于"每个站点跑 $O(\log N)$ 个虚拟节点来获得负载均衡"，那样做的目的是在部署节点很少的情况下测扩展性。

中位延迟在 180 到 285 ms 之间（随节点数变化）。对 180 个节点这一档：一次典型查找涉及五次双向消息交换 —— 四次用于 Chord 查找、最后一次发给 successor 节点；站点间典型往返延迟 60 ms；于是预期查找时间约 300 ms，与测得的中位 285 ms 接近。低 5 百分位来自"key 在 ID 空间上离查询节点很近"以及"跳数停留在本物理站点内"；高 95 百分位来自走了高延迟路径的那些跳。

相关

• CAN —— 同年（SIGCOMM 2001）的另一条路，正好构成正面对照：CAN 放弃 $O(\log N)$ 的路径长度，换来每节点状态与 $n$ 无关（$2d$ 个邻居）；Chord 接受 $O(\log N)$ 状态以换对数级路径。CAN 把位置摊在 $d$ 维坐标空间里（邻居靠几何关系），Chord 把位置摊在一维环上（邻居靠 finger 的 2 的幂结构）
• 一致性哈希算法 —— 本专栏的前置：那篇讲的环、虚拟节点、重映射界，正是 Chord 直接拿来用的工具。Chord 的增量在于**"每个节点不必知道几乎所有其他节点"** —— 用 finger table 把查找变成 $O(\log N)$
• Dynamo —— 一致性哈希在生产系统里的用法：Dynamo 同样用环 + 虚拟节点，但它为了写可用性放弃了强一致（用向量时钟与 sloppy quorum 处理冲突），而 Chord 只是查找原语、不承诺任何数据语义（认证/缓存/复制全交给应用）
• Cassandra —— 从 Dynamo 那条线演化，但它把随机哈希换成了保序哈希 —— 这个改动正是为了让范围查询能在环上顺序进行，代价是放弃了"哈希均匀"带来的负载均衡
• Ceph —— CRUSH 与本篇的 finger table 是两种"让节点自己算出位置"的结构：CRUSH 是纯函数、节点之间不需要维持路由表，代价是必须有一张分层的 cluster map；Chord 的路由表是动态维护的局部状态，代价是稳定化协议

参考

• I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, H. Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. SIGCOMM 2001.

贡献者

YJ

文件历史

最后编辑于 2 天前查看完整历史

ae1ee-docs：内容完善

448f1-分布式